package com.code.leetcode.offer;

import java.util.PriorityQueue;
import java.util.Queue;

/**
 * @author codeDorado
 * @version 1.0
 * @date 2020/8/2 16:46
 *  这里很巧妙的用了 最小堆 和 最大堆 的方式来进行对数据的分段
 *  利用优先队列 PriorityQueue 进行排序
 *  利用 q1 与 q2 的 size 差别来进行对哪个队列进行存数据
 */
public class The41_priorityqueue {

    Queue<Integer> queue1, queue2;
    /** initialize your data structure here. */
    public The41_priorityqueue() {
        queue1 = new PriorityQueue<>();
        queue2 = new PriorityQueue<>((x, y) -> y - x);
    }

    public void addNum(int num) {
        if (queue1.size() != queue2.size()) {
            queue1.add(num);
            queue2.add(queue1.poll());
        } else {
            queue2.add(num);
            queue1.add(queue2.poll());
        }
    }

    public double findMedian() {
        return queue1.size() != queue2.size() ? queue1.peek() : (queue1.peek() + queue2.peek()) / 2.0;
    }
}
